package com.atguigu.linkedlist;

import java.util.Stack;

/**
 * @author Amos
 * @date 2022/5/30
 */

public class SingleLinkedListDemo {
    public static void main(String[] args) throws InterruptedException {
        // 进行测试
        // 先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        // 创建链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();

        // 加入
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero4);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);

        // 加入按照编号的顺序
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);
//        singleLinkedList.addByOrder(hero3); // 用于测试重复添加数据

        // 更新测试
        singleLinkedList.update(new HeroNode(2, "zjh", "amos"));

        // 删除测试
//        singleLinkedList.del(3);
//        singleLinkedList.del(1);

        // 测试链表节点个数的方法
//        System.out.println(SingleLinkedList.getLength(singleLinkedList.getHead()));
//        System.out.println(singleLinkedList.countList());

        System.out.println("查找的倒数元素为" + singleLinkedList.theInverseKth(5));

        // 显示一把
        singleLinkedList.list();

        // 反转链表测试
//        System.out.println("反转后的链表为：");
//        singleLinkedList.reverse(singleLinkedList.getHead());
        System.out.println("~~~~~~~~~~~~~");
        singleLinkedList.reversedList(singleLinkedList.getHead());
        singleLinkedList.list();
        System.out.println("^^^^^^^^^^^^^");

        System.out.println("遍历现在的链表");
        singleLinkedList.list();
        System.out.println("使用栈结构反向遍历链表：百度面试题");
        reversePrint(singleLinkedList.getHead());

        // 测试合并两个有序链表
        System.out.println("=================start==================");
        HeroNode v2 = new HeroNode(2, "v2", "v2");
        HeroNode v5 = new HeroNode(5, "v5", "v5");
        HeroNode v9 = new HeroNode(9, "v9", "v9");
        HeroNode v3 = new HeroNode(3, "v3", "v3");
        HeroNode v4 = new HeroNode(4, "v4", "v4");
        HeroNode v7 = new HeroNode(7, "v7", "v7");
        HeroNode v92 = new HeroNode(9, "v9", "v9");
        HeroNode v10 = new HeroNode(10, "v10", "v10");
        HeroNode v12 = new HeroNode(12, "v12", "v12");


        SingleLinkedList slList1 = new SingleLinkedList();
        SingleLinkedList slList2 = new SingleLinkedList();

        slList1.add(v2);
        slList1.add(v5);
        slList1.add(v9);
        slList1.list();

        slList2.add(v3);
        slList2.add(v4);
        slList2.add(v7);
        slList2.add(v92);
        slList2.add(v10);
        slList2.add(v12);
        slList2.list();

        HeroNode combineNode = combine(slList1.getHead(), slList2.getHead());
        System.out.println("遍历合并后的节点");
        HeroNode cTemp = combineNode.next;
        while (cTemp != null) {
            System.out.println(cTemp.no);
            cTemp = cTemp.next;
        }

        System.out.println("=================end==================");


    }
    public static void reversePrint(HeroNode head) {
        if (head.next == null) {
            return; // 空链表，不能打印
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
    public static HeroNode combine(HeroNode head1, HeroNode head2) {
        HeroNode head = new HeroNode(0, "", "");
        HeroNode h = head.next;
        HeroNode h1 = head1.next;
        HeroNode h2 = head2.next;
        if (h1 == null) return head2;
        if (h2 == null) return head1;
        while (true) {
            if (h1.no <= h2.no) {
                h = h1;
                h1 = h1.next;
                if (h1 == null) {
                    h = h2.next;
                    System.out.println("合并节点为：" + h);
                    break;
                }
                System.out.println("合并节点为：" + h);
                h = h.next;
            }
            if (h1.no > h2.no) {
                h = h2;
                h2 = h2.next;
                if (h2 == null) {
                    h = h1.next;
                    System.out.println("合并节点为：" + h);
                    break;
                }
                System.out.println("合并节点为：" + h);
                h = h.next;
            }
        }
        return head;
    }
}

// 定义SingleLinkedList 管理我们的英雄
class SingleLinkedList {
    // 先初始化一个头结点，头结点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    public HeroNode getHead() {
        return head;
    }

    // 添加节点到单向链表
    // 思路，当不考虑顺序编号时
    // 1. 找到当前链表的最后节点
    // 2. 将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode) {
        // 因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        // 遍历链表，找到最后
        while (true) {
            // 找到链表的最后
            if (temp.next == null) {
                break;
            }
            // 如果没有找到最后，将temp后移
            temp = temp.next;
        }
        // 当退出while循环时,temp就指向了链表的最后
        // 将最后这个节点的next指向新的节点
        temp.next = heroNode;
    }

    // 第二种添加英雄方式，根据排名将英雄插入到指定位置
    // 如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HeroNode heroNode) {
        // 因为头结点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
        // 因为单向链表，我们找到的temp是位于添加位置的前一个节点，否则插入不了
        HeroNode temp = head;
        boolean flag = false; // flag标志添加的编号是否存在，默认为false
        while (true) {
            if(temp.next == null) { // 说明temp已经在链表的最后
                break;
            }
            if (temp.next.no > heroNode.no) { // 位置找到，就在temp的后面插入
                break;
            } else if (temp.next.no == heroNode.no) { // 说明希望添加的heroNode的编号已然存在
                flag = true; // 说明编号存在
                break;
            }
            temp = temp.next; // 后移，遍历当前链表
        }
        // 判断flag的值
        if (flag) { // 不能添加，说明编号存在
            System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入\n",heroNode.no);
        } else {
            // 插入到链表中，在temp的后面
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }



    public void myAddByOrder(HeroNode newNode) throws InterruptedException {
        HeroNode temp = head;
        int countloop = 0;
        if (temp.next == null) {
            temp.next = newNode;
            return;
        }
        while (true) {
            if (newNode.no <= temp.next.no) {
                newNode.next = temp.next;
                temp.next = newNode;
                return;
            }
//            else if(newNode.no == temp.next.no) {
//                System.out.println("数据已存在，不添加重复元素");
//                return;
//            }

            else {
                temp = temp.next;
                if (temp.next == null) {
                    temp.next = newNode;
                    return;
                }
                System.out.println("other结果为：" + countloop++);
            }
        }


    }

    // 修改节点的信息，根据no编号来修改，即no不能修改
    // 说明
    // 1. 根据newHeroNode的no来修改即可
    // 不够完善，如果没有需要修改的节点，没有提示信息，可以增加flag信息进行记录
    public void MyUpdate(HeroNode newHeroNode) {
        HeroNode temp = head;
        if (temp.next == null) {
            System.out.println("链表为空，无法进行更新操作");
            return;
        }
        while (true) {
            if (temp.next.no == newHeroNode.no) {
                newHeroNode.next = temp.next.next;
                temp.next = newHeroNode;
            }
            temp = temp.next;
            if (temp.next == null) {
                break;
            }
        }
    }

    // 韩老师的代码
    public void update(HeroNode newHeroNode) {
        // 判断是否为空
        if (head.next == null) {
            System.out.println("链表为空~");
            return;
        }
        // 找到需要修改的节点，根据no编号
        // 定义一个辅助变量
        HeroNode temp = head.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break; // 已经遍历万链表
            }
            if (temp.no == newHeroNode.no) {
                // 找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag判断是否找到需要修改的节点
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else { // 没有找到
            System.out.printf("没有找到编号%d的节点，不能修改", newHeroNode.no);
        }
    }

    // 删除节点
    // 思路
    // 1. head不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
    // 2. 说明我们在比较时，是temp.next.no和需要删除的节点的no比较
    public void MyDel(int no) {
        if (head.next == null) {
            System.out.println("链表为空");
        }
        HeroNode temp = head;
        int toBeDelCount = 0;
        while (true) {
            if (temp.next.no == no) {
                temp.next = temp.next.next;
                toBeDelCount++;
                System.out.printf("已删除节no为%d的节点%d个\n", no, toBeDelCount);
            }
            temp = temp.next;
            if (temp.next == null) {
                break;
            }
        }
    }

    public void del(int no) {
        HeroNode temp = head;
        boolean flag = false;
        while (true) {
            if (temp.next == null) { // 已经到链表的最后
                break;
            }
            if (temp.next.no == no) {
                // 找到的待删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next; // temp后移，遍历
        }
        // 判断flag
        if (flag) { // 找到
            temp.next = temp.next.next;
        }

    }

    // 显示链表[遍历]
    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 因为头结点不能动，因此我们需要一个辅助变量来遍历
        HeroNode temp = head.next;
        while (true) {
            // 判断是否到链表最后
            if (temp == null) {
                break;
            }
            // 输出节点信息
            System.out.println(temp);
            // 将temp后移，一定小心
            temp = temp.next;
        }
    }

    // 用更简短的代码实现list(), 另外初始temp指向了head节点，而不是head.next，并且将temp.next作为循环条件
    public void myList() {
        HeroNode temp = head;
        if (temp.next == null) {
            System.out.println("空链表");
            return;
        }
        while (temp.next != null) {
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

    // 计算节点总数
    public int countList() {
        int sum = 0;
        HeroNode temp = head;
        if (temp.next == null) {
            return 0;
        }
        while (true) {
            if (temp.next != null) {
                sum++;
            }
            temp = temp.next;
            if (temp.next == null) {
                break;
            }
        }
        return sum;
    }
    // 方法：获取到单链表的节点个数，头结点不计入在内

    /**
     *
     * @param head 链表的头结点
     * @return 返回的就是有效节点的个数
     */
    public static int getLength(HeroNode head) {
        if (head.next == null) { // 空链表
            return 0;
        }
        int length = 0;
        // 定义一个辅助变量, 没有统计头结点
        HeroNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next; // 遍历
        }
        return length;
    }

    public HeroNode theInverseKth(int k) {
        if (head.next == null) {
            System.out.println("链表为空，无法查找");
            return null;
        }
        if (k < 1 || k > getLength(head)) {
            System.out.printf("请提供[1,%d]范围内的k值",getLength(head));
            return null;
        }
        HeroNode temp = head.next;
        for ( int i = 0; i < getLength(head) - k; i++) {
            temp = temp.next;
        }
        return temp;
    }

    // 链表倒序
    public void reverse(HeroNode head) {
        SingleLinkedList slList = new SingleLinkedList();
        for (int i = 1; i <= getLength(head); i++) {
            System.out.println("过程打印：" + theInverseKth(i));
        }
    }

    // 使用临时的头结点来反转链表
    public void reversedList(HeroNode head) {
        HeroNode cur = head.next;
        HeroNode t;
        HeroNode reversedHead = new HeroNode(0, "", "");

        if (head.next == null || head.next.next == null) {
            return;
        }

        while (cur != null) {
            t = cur.next;
            cur.next = reversedHead.next;
            reversedHead.next = cur;
            cur = t;
        }
        head.next = reversedHead.next;
    }



}




// 定义HeroNode，每个HeroNode对象就是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next; // 指向下一个节点

    // 构造器
    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
